'''
@author: Kevin Zhao
@data:Nov 26,2012 
@note:
maximum sub-array

Exercise 4.1-2,4.1-3,4.1-4 ,4.1-5
'''
import math
import sys

'''
Exercise 4.1-2
Brute force version of max_sub_array algorithm
'''
def max_subarray_bruteforce(array):
    max_sum = 0
    L_index = 0
    R_index = 0
    R_temp_index = 0
    for i in range(0, len(array) - 2):
        temp_sum = array[i]
        for j in range(i + 1, len(array) - 1):
                R_temp_index = j
                temp_sum = temp_sum + array[j]
        
                if temp_sum > max_sum:
                    L_index = i
                    R_index = R_temp_index
                    max_sum = temp_sum
            
    return ', '.join([str(x) for x in array[L_index:R_index + 1]]) + ',sum:' + str(max_sum)


'''
Find subarrays that locate across the mid point
'''
def find_cross_max(l_index, r_index, mid_index, array):
    max_l_sum = -sys.maxint #negative infinity
    max_r_sum = -sys.maxint #negative infinity
    l_sum_temp = r_sum_temp = 0
    max_l_index = mid_index
    max_r_index = mid_index + 1
    
    for i in range(mid_index, l_index - 1, -1):
        l_sum_temp = l_sum_temp + array[i] 
        if l_sum_temp >= max_l_sum:
            max_l_index = i
            max_l_sum = l_sum_temp
        
    for j in range(mid_index + 1, r_index + 1):
        r_sum_temp = r_sum_temp + array[j]
        if r_sum_temp >= max_r_sum:
            max_r_index = j
            max_r_sum = r_sum_temp
    
    return max_l_index, max_r_index, max_l_sum + max_r_sum #tuple (l_index,r_index,sum)

'''
Exercise 4.1-3
Recursive version of max_sub_array algorithm
'''
def msaR(l_index, r_index, array):
    #base case
    if l_index == r_index:
        return l_index, r_index, array[l_index]#tuple (l_index,r_index,sum)
    #divide
    mid_index = int(math.floor((l_index + r_index) / 2)) 
    
    left_array_tuple = msaR(l_index, mid_index, array)
    right_array_tuple = msaR(mid_index + 1, r_index, array)
    cross_array_tuple = find_cross_max(l_index, r_index, mid_index, array)
    #combine
    if left_array_tuple[2] > right_array_tuple[2] and left_array_tuple[2] > cross_array_tuple[2]:
        return left_array_tuple
    elif  right_array_tuple[2] > left_array_tuple[2] and right_array_tuple[2] > cross_array_tuple[2]:
        return right_array_tuple
    else:
        return cross_array_tuple
    
'''
Exercise 4.1-5
Non-recursive and Linear-time algorithm for finding the max sub_array
1.Idea:
Iterate through the list, keeping track of the local sum of the list elements so far.
If the local sum is the highest sum so far, then keep a record of it. 
If the local sum reaches 0 or below, then reset it and restart from the next element.

2.Theory:
If the current subset sum is greater than zero it will contribute to future subset sums, 
so we keep it. On the other hand if the current subset sum is zero or below it will not 
contribute to future subset sums. So we throw it away and start fresh with a new subset 
sum. Then it's just a matter of keeping track of when the current subset sum is greater 
then any previous encountered.

3.Reference:
http://stackoverflow.com/questions/12165795/random-integers-in-array-find-the-greatest-sum-of-a-continuous-subset
'''
def msaL(array):
    local_start = max_start = max_end = 0
    max_sum = -sys.maxint
    local_sum = 0
    arr_len = len(array)
    
    for i in range(arr_len - 1):
        local_sum = local_sum + array[i]
        if local_sum > max_sum:
            max_end = i
            max_sum = local_sum
            max_start = local_start
        if local_sum < 0:
            local_start = i + 1
            local_sum = 0
            
    return max_start, max_end, max_sum


#test
array = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
print msaR(0, len(array) - 1 , array)
print max_subarray_bruteforce(array)
print msaL(array)
